package algorithm.problems.tree;

/**
 * Created by gouthamvidyapradhan on 19/08/2017.
 * Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
 * <p>
 * The root is the maximum number in the array.
 * The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
 * The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
 * Construct the maximum tree by the given array and output the root node of this tree.
 * <p>
 * Example 1:
 * Input: [3,2,1,6,0,5]
 * Output: return the tree root node representing the following tree:
 * <p>
 * 6
 * /   \
 * 3     5
 * \    /
 * 2  0
 * \
 * 1
 * <p>
 * Note:
 * The size of the given array will be in the range [1,1000].
 */
public class MaximumBinaryTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private int[][] max;

    /**
     * Main method
     *
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        int[] nums = {3, 2, 1, 6, 0, 5};
        TreeNode root = new MaximumBinaryTree().constructMaximumBinaryTree(nums);
        System.out.println(root.val); //print root
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {

        max = new int[nums.length][nums.length];

        //pre-fill with initial values
        for (int i = 0; i < nums.length; i++) {
            max[i][i] = i;
        }

        //pre-calculate max for range index
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                max[i][j] = nums[max[i][j - 1]] > nums[j] ? max[i][j - 1] : j;
            }
        }

        return build(0, nums.length - 1, nums);
    }

    private TreeNode build(int s, int e, int[] nums) {
        if (s <= e) {
            int val = nums[max[s][e]];
            TreeNode n = new TreeNode(val);
            n.left = build(s, max[s][e] - 1, nums);
            n.right = build(max[s][e] + 1, e, nums);
            return n;
        }
        return null;
    }

}
